using System;
using System.Collections.Generic;
using System.Text;

namespace RikMigrations
{
	public class CircularDependencyException : Exception
	{
	}

	// TODO: This whole class is a rather ordinary hack and needs to be properly designed and implemented
	public class DependencyTree<T>
	{
		List<Node> roots = new List<Node>();

		public void Add(T value, params T[] dependsOn)
		{
			Add(value, new List<T>(dependsOn));
		}

		public void Add(T value, List<T> dependsOn)
		{
			if (dependsOn == null || dependsOn.Count == 0)
			{
				if (Find(value) == null)
					AddRoot(value);
			}
			else
			{
				List<Node> parents = new List<Node>();
				foreach (T d in dependsOn)
				{
					if (d.Equals(value))
						throw new ArgumentException("Unable to depend on itself");
					Node p = Find(d);
					if (p == null)
						parents.Add(AddRoot(d));
					else
					{
						if (p.HasParent(value))
							throw new CircularDependencyException();
						parents.Add(p);
					}
				}

				Node newNode = Find(value);
				if (newNode == null)
					newNode = new Node(value);
				else
					roots.Remove(newNode);
				foreach (Node parent in parents)
				{
					parent.Children.Add(newNode);
					newNode.Parents.Add(parent);
				}
			}
		}

		Node AddRoot(T value)
		{
			Node newNode = new Node(value);
			roots.Add(newNode);
			return newNode;
		}

		Node Find(T value)
		{
			foreach (Node n in GetValues())
				if (n.Value.Equals(value))
					return n;
			return null;
		}

		IEnumerable<Node> GetValues()
		{
			List<Node> visited = new List<Node>();
			foreach (Node n in roots)
				if (!visited.Contains(n))
				{
					visited.Add(n);
					yield return n;
					foreach (Node n2 in n.GetValues(visited))
						yield return n2;
				}
		}

		public IEnumerable<T> VisitAllNodes()
		{
			foreach (Node n in roots)
			{
				yield return n.Value;
				foreach (Node n2 in n.VisitAllNodes())
					yield return n2.Value;
			}
		}

		class Node
		{
			public T Value;
			public List<Node> Parents = new List<Node>();
			public List<Node> Children = new List<Node>();

			public Node(T value)
			{
				this.Value = value;
			}

			public bool HasParent(T value)
			{
				foreach (Node parent in Parents)
					if (parent.Value.Equals(value) || parent.HasParent(value))
						return true;
				return false;
			}

			public IEnumerable<Node> GetValues(List<Node> visited)
			{
				foreach (Node n in Children)
					if (!visited.Contains(n))
					{
						visited.Add(n);
						yield return n;
						foreach (Node n2 in n.GetValues(visited))
							yield return n2;
					}
			}

			public IEnumerable<Node> VisitAllNodes()
			{
				foreach (Node n in Children)
				{
					yield return n;
					foreach (Node n2 in n.VisitAllNodes())
						yield return n2;
				}
			}
		}
	}
}